package com.c2b.algorithm.leetcode.lcr;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">合并 K 个升序链表(Merge k Sorted Lists)</a>
 * <p>给你一个链表数组，每个链表都已经按升序排列。</p>
 * <p>请你将所有链表合并到一个升序链表中，返回合并后的链表。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：lists = [[1,4,5],[1,3,4],[2,6]]
 *      输出：[1,1,2,3,4,4,5,6]
 *      解释：链表数组如下：
 *          [
 *            1->4->5,
 *            1->3->4,
 *            2->6
 *          ]
 *          将它们合并到一个有序链表中得到。
 *          1->1->2->3->4->4->5->6
 *
 * 示例 2：
 *      输入：lists = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：lists = [[]]
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>k == lists.length</li>
 *      <li>0 <= lists[i].length <= 500</li>
 *      <li>-10^4 <= lists[i][j] <= 10^4</li>
 *      <li>lists[i] 按 升序 排列</li>
 *      <li>lists[i].length 的总和不超过 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/20 14:46
 */
public class LCR078 {
    static class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return merge(lists, 0, lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left == right) {
                return lists[left];
            }
            if (left > right) {
                return null;
            }
            int mid = left + ((right - left) >> 1);
            return mergeTwoSortedList(merge(lists, left, mid), merge(lists, mid + 1, right));
        }

        private ListNode mergeTwoSortedList(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            ListNode dummyHead = new ListNode();
            ListNode currNode = dummyHead;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    currNode.next = list1;
                    list1 = list1.next;
                } else {
                    currNode.next = list2;
                    list2 = list2.next;
                }
                currNode = currNode.next;
            }
            if (list1 != null) {
                currNode.next = list1;
            }
            if (list2 != null) {
                currNode.next = list2;
            }
            return dummyHead.next;
        }
    }
}
